#include "./huffman-tree.h"
#include <iostream>

void select(HNode *nodes, int count, int &n1, int &n2)
{
	// 先找到没有父结点的结点中的第一个
	for (int i = 0; i < count; i++)
	{
		if (nodes[i].parent == nullptr)
		{
			n1 = i;
			break;
		}
	}
	// 找到第一个最小的
	for (int i = n1 + 1; i < count; i++)
	{
		if (nodes[i].parent == nullptr && nodes[i].weight < nodes[n1].weight)
		{
			n1 = i;
		}
	}
	// 找到没有父节点且不等于第一个最小的结点的结点
	for (int i = 0; i < count; i++)
	{
		if (nodes[i].parent == nullptr && nodes[i].weight != nodes[n1].weight)
		{
			n2 = i;
			break;
		}
	}
	// 找到第二个最小的，但是大于第一个
	for (int i = n2 + 1; i < count; i++)
	{
		if (nodes[i].parent == nullptr && nodes[i].weight < nodes[n2].weight && i != n1)
		{
			n2 = i;
		}
	}
}

void createHuffmanTree(HuffmanTree &tree, ElemType *e, int *weight, int count)
{
	// 所有结点数
	int total = 2 * count - 1;
	// 初始化结点
	HNode *nodes = (HNode *)calloc(total, sizeof(HNode));
	for (int i = 0; i < count; i++)
	{
		nodes[i].data = e[i];
		nodes[i].weight = weight[i];
		nodes[i].parent = nodes[i].lchild = nodes[i].rchild = nullptr;
	}
	// 开始构建
	// 每次合并后的结点放在node[n]开始及其之后的一共n - 1个位置中，因此从下标从n开始到2n - 2
	int n1, n2; // 表示第一小和第二小的结点
	for (int i = count; i < total; i++)
	{
		// 选择
		select(nodes, i, n1, n2);
		// 合并
		nodes[i].data = 0;
		nodes[i].weight = nodes[n1].weight + nodes[n2].weight;
		nodes[i].lchild = &nodes[n1];
		nodes[i].rchild = &nodes[n2];
		nodes[n1].parent = nodes[n2].parent = &nodes[i];
	}
	// 最后，找到根节点返回
	for (int i = 0; i < total; i++)
	{
		if (nodes[i].parent == nullptr)
		{
			tree = &nodes[i];
			return;
		}
	}
}

void preOrderTraverse(HuffmanTree &tree, void (*visit)(HNode *e))
{
	if (tree != nullptr)
	{
		// 先访问根节点
		visit(tree);
		// 然后依次遍历左右子树
		preOrderTraverse(tree->lchild, visit);
		preOrderTraverse(tree->rchild, visit);
	}
}

void inOrderTraverse(HuffmanTree &tree, void (*visit)(HNode *e))
{
	if (tree != nullptr)
	{
		// 先遍历左子树
		inOrderTraverse(tree->lchild, visit);
		// 然后访问根节点
		visit(tree);
		// 然后遍历右子树
		inOrderTraverse(tree->rchild, visit);
	}
}

void postOrderTraverse(HuffmanTree &tree, void (*visit)(HNode *e))
{
	if (tree != nullptr)
	{
		// 先遍历左子树
		postOrderTraverse(tree->lchild, visit);
		// 然后遍历右子树
		postOrderTraverse(tree->rchild, visit);
		// 然后访问根节点
		visit(tree);
	}
}